The authentication of messages exchanged over public channels is an important goal in cryptography. A message is authenticated when both the integrity and the authenticity of the message are verified. The integrity of a message is verified when the message has not been modified, and the authenticity of a message is verified when the message is confirmed to be sent by the purported sender. Typically, a sender of a message encrypts the message, generates a message authentication code (“MAC”) from the message, and transmits the encrypted message and the MAC to a receiver. The receiver uses the MAC to authenticate the message. Many algorithms have been designed for the sole purpose of authenticating. Based on needed security, MACs can be either unconditionally or computationally secure. Unconditionally secure MACs are secure against forgers with unlimited computational power, while computationally secure MACs are secure only when forgers have limited computational power.
A popular class of unconditionally secure MAC algorithms is based on universal hash-function families developed by Carter and Wegman. (Carter, J., Wegman, M., “Universal Classes of Hash Functions,” in Proceedings of the 9th Annual ACM Symposium on Theory of Computing—STOC '77, pp. 106-112, ACM (1977).) The basic concept allowing for unconditional security is that the authentication key can be used to authenticate only a limited number of exchanged messages. Since the management of one-time keys is considered impractical in many applications, computationally secure MACs, rather than unconditionally secure MACs, are used for most practical applications. With computationally secure MACs, keys can be used to authenticate an arbitrary number of messages. That is, after agreeing on a key, legitimate users can exchange an arbitrary number of authenticated messages with the same key. Computationally secure MACs can be classified into three main categories: block cipher, cryptographic hash function, or universal hash-function family.
The cipher-block chaining MAC (“CBC-MAC”) is one of the most well-known block cipher based MACs. The CBC-MAC is specified in many governmental and international standards. The exclusive OR (“XOR-MAC”) and parallelizable MAC (“PMAC”) are other well-known block ciphers.
The use of one-way cryptographic hash functions for message authentication was introduced by Tsudik. Examples of cryptographic hash functions for MACs include the hash-based MAC (“HMAC”) and the message digest x MAC (“MDx-MAC”), which are specified in the International Organization for Standardization ISO/IEC 9797-2.
The use of universal hash-function families in the Carter-Wegman style is not restricted to the design of unconditionally secure MACs. Rather, computationally secure MACs based on universal hash functions can be constructed with two rounds of computations. In the first round, the message to be authenticated is compressed using a universal hash function. Then, in the second round, the compressed image is processed with a cryptographic function (e.g., a pseudorandom function).
Indeed, universal hashing based MACs give better performance when compared to block cipher or cryptographic hashing based MACs. There are two main factors leading to the performance advantage of universal hashing based MACs. First, processing messages block by block using universal hash functions is faster than processing messages block by block using block ciphers or cryptographic hash functions. Second, since the output of the universal hash function is much shorter than the original message itself, processing the compressed image with a cryptographic function can be performed efficiently.
One of the main differences between unconditionally secure MACs based on universal hashing and computationally secure MACs based on universal hashing is the requirement to process the compressed image with a cryptographic primitive with the computationally secure MACs. This round of computation is necessary to protect the secret key of the universal hash function. That is, since universal hash functions are not cryptographic functions, the observation of multiple message image pairs can reveal the value of the hashing key. Since the hashing key is used repeatedly in computationally secure MACs, the exposure of the hashing key will lead to breaking the security of the MAC. Thus, processing the compressed image with a cryptographic primitive is necessary for the security of this class of MACs. This implies that unconditionally secure MACs based on universal hashing are more efficient than computationally secure ones. On the negative side, unconditionally secure universal hashing based MACs are considered impractical in most modern applications, due to the difficulty of managing one-time keys.
A couple of observations can be made about existing MAC algorithms. First, they are designed independently of any other operations required to be performed on the message to be authenticated. For example, if the authenticated message must also be encrypted, existing MACs are not designed to utilize the functionalities that can be provided by the underlying encryption algorithm. Second, most existing MACs are designed for general computer communication systems, independently of the properties that messages can possess. For example, most existing MACs are inefficient when the messages to be authenticated are short.
There is, however, an increasing demand for the deployment of networks consisting of a collection of small devices. In many practical applications, the main purpose of such devices is to communicate short messages. A sensor network, for example, can be deployed to monitor certain events and report some collected data. In many sensor network applications, reported data consist of short confidential measurements. For example, the ability to authenticate messages in a sensor network deployed in a battlefield with the purpose of reporting the existence of moving targets or other temporal activities is of critical importance. In another application, the radio frequency identification (RFID) systems also send short confidential messages. In such systems, RFID readers need to identify RFID tags. In such scenarios, RFID tags usually encrypt their identity, which is typically a short string, to protect their privacy. Since the RFID readers also authenticate the identity of the RFID tag, RFID tags are equipped with a message authentication mechanism. Another application that is becoming increasingly important is the deployment of body sensor networks. In such body sensor networks, small sensors are embedded in a patient to report some vital signs. The confidentiality and integrity of such reported messages can be important.
Significant effort has been devoted to the design of hardware efficient implementations for such small devices. For example, many hardware efficient implementations of block ciphers and cryptographic hash functions have been proposed. However, little or no effort has been devoted to the design of algorithms for message authentication codes for such networks. Because of the computational expense of existing MAC techniques, it would be desirable to have a technique for authenticating short encrypted messages that is more efficient than existing MAC algorithms.